package com.order.www;

/**
 * Creared with IntelliJ IDEA.
 * Description:输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
 * User:yxd
 * Date:2022-02-09
 * Time:12:42
 */
public class Array5 {
    public static void main(String[] args) {
        int[] array = {1,-2,3,10,-4,7,2,-5};
        System.out.println(FindGreatestSumOfSubArray(array));
    }
    public static int FindGreatestSumOfSubArray(int[] array) {
        /*int val = array[0];
        int[] dp = new int[array.length];
        dp[0] = array[0];
        for(int i = 1;i < array.length;i ++){
            dp[i] = Math.max(dp[i - 1] + array[i],array[i]);//从前面往后面一个个相加如果前面所有值更小就更换为当前值为开始
            if(val < dp[i]){
                val = dp[i];
            }
        }
        return val;*/
        int val = array[0];
        int max_val = array[0];
        for(int i = 1;i < array.length;i ++){
            if(val > 0){//看前面的所有值相加有无贡献，如果小于0就更换为当前值，相比上面减少了内存消耗
                val += array[i];
            }else{
                val = array[i];
            }
            if(max_val < val){
                max_val = val;
            }

        }
        return max_val;
    }

}
